import java.util.Random;

import static java.util.Arrays.sort;
import static java.util.Collections.swap;

//快速排序
//https://leetcode.cn/problems/sort-an-array/
public class Test {
    public static void main(String[] args) {
        //
    }
}

class Solution {
    public int[] sortArray(int[] nums) {
        sort(nums,0,nums.length-1);
        return nums;
    }




    //递归
    //这里边的l、r、left、right，太多小细节了，写错了好多处，对照着老师的改的
    public void sort(int[] nums, int l, int r) {
        int i = l;
        int left = l-1, right = r+1;
        int key = nums[new Random().nextInt(right - left + 1) + left];//随机指定一个key
        while (i < r) {
            if (nums[i] < key) {
                swap(i,++left,nums);
            }else if (nums[i] > key) {
                swap(i,--right,nums);
            }else{
                i++;
            }
        }
        //[l,left] [left+1,right-1] [right,r]——这里的逻辑尤其重要，不能只知其形，不知其意，只是抄老师这里的注释格式！！！
        sort(nums,l,left);
        sort(nums,right,r);

    }

    //交换函数
    public void swap(int i, int j, int[] nums){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

    /*//随机选择一个数（合规的）
    public int randomKey(int right, int left,int[] nums){
        Random random = new Random();

        // 生成一个随机整数
        int randomInt = random.nextInt();
        int index = randomInt%(right - left + 1);
        return nums[index];
    }*/
}